package org.basis.algorithm.sort;

import org.basis.algorithm.common.SortUtil;

/**
 * heapInsert操作
 *
 * @author Mr_wenpan@163.com 2021/12/06 18:16
 */
public class HeapInsert {

    public static void main(String[] args) {

        int[] arr = SortUtil.generateRandomArray(20, 20);
        for (int i = 0; i < 20; i++) {
            heapInsert(arr, i);
        }
        SortUtil.printArr(arr);
    }

    /**
     * 某个数现在处在index位置，往上继续移动，直到不大于父节点
     *
     * @param arr   已经是堆结构的数组
     * @param index 插入元素的下标
     */
    private static void heapInsert(int[] arr, int index) {
        // 大于父节点
        while (arr[index] > arr[(index - 1) / 2]) {
            // 和父节点交换
            SortUtil.swap(index, (index - 1) / 2, arr);
            // 当前索引位置更改
            index = (index - 1) / 2;
        }
    }

    private static void heapify(int[] arr, int index, int heapSize) {
        // 左孩子
        int left = 2 * index + 1;
        // 有孩子
        while (left < heapSize) {
            // 找到两个孩子中值最大的孩子的下标
            // 有右孩子？
            int largest = left + 1 < heapSize ? (arr[left] > arr[left + 1] ? left : left + 1) : left;

            // 最大的孩子都不比自己大，则不换
            if (arr[largest] <= arr[index]) {
                break;
            }

            // 交换两个位置的值
            SortUtil.swap(index, largest, arr);
            // 重置自己的下标和左孩子下标
            index = largest;
            left = 2 * index + 1;
        }

    }

    private static void heapInsert1(int[] arr, int index) {
        // 大于父节点就和父节点换位
        while (arr[index] > arr[(index - 1) / 2]) {
            SortUtil.swap(index, (index - 1) / 2, arr);
            index = (index - 1) / 2;
        }
    }

    private static void heapify1(int[] arr, int index, int heapSize) {

        int leftChild = 2 * index + 1;
        while (leftChild < heapSize) {
            // 最大孩子的下标，先看看有没有右孩子，如果有那么就取左右孩子中值最大的那个为largest
            int largest = leftChild + 1 >= heapSize ? leftChild : (arr[leftChild] > arr[leftChild + 1] ? leftChild : leftChild + 1);
            if (arr[largest] <= arr[index]) {
                break;
            }
            // 和最大的孩子交换
            SortUtil.swap(largest, index, arr);
            index = largest;
            leftChild = 2 * index + 1;
        }

    }

}
